\section{Descripci\'on del Problema}
Se cuenta con una red de computadoras interconectada por enlaces con un costo asociado. Basándonos en esta configuración se debe generar una red con las siguientes características:
\begin{itemize}
\item Un grupo de computadoras debe estar interconectada en configuración de anillo, es decir, cada máquina debe tener dos caminos distintos para llegar a cualquier otra perteneciente al anillo.
\item El resto debe tener acceso a alguna computadora del anillo, ya sea por un enlace directo o a través de una máquina que no pertenezca.
\item Se debe minimizar el costo total de los enlaces en la estructura resultante.
\end{itemize}

\section{Idea General de la Resoluci\'on}
Se modela el problema con grafos, siendo cada computadora un nodo y cada enlace una arista.
Para minimizar el costo total, se deben elegir los enlaces con menor costo procurando mantener a todas las computadoras conectadas y a un subconjunto de ellas, formando un anillo.

Buscando un Árbol Generador Mínimo(AGM) en nuestro modelo, nos garantizamos que todos los nodos estén interconectados minimizando el costo de aristas. Nos faltaría definir que nodos formarán el anillo, en nuestro grafo, un ciclo, de manera tal que el costo sea mínimo. Esto lo resolvemos agregando una arista que no pertenezca al árbol resultante, ya que, por definición de árbol, al hacerlo se forma un ciclo. Esta arista es la que tiene menor peso de entre las que no componen al árbol.

Por último, se requiere diferenciar los nodos que pertenecen al anillo de los que no, para esto hacemos un DFS\footnote{Depth First Search - búsqueda en profundidad.} empezando por uno de los extremos de la arista que forma el ciclo, registrando el orden de exploración de los nodos. Al finalizar, recorremos la estructura que contiene el órden, desde el nodo final(el otro extremo de la arista) hacia el inicial. 
\subsection{Pseudoc\'odigo}
En \ref{alg:ej3:kruskal} vemos el algoritmo principal. Este algoritmo es una modificación del algoritmo de Kruskal para encontrar AGM. La diferencia radica en que cuando se encuentra la primer arista que forma un ciclo, se hace un DFS(Ver \ref{alg:ej3:dfs}) fijando como nodo raíz un extremo de esta y luego recorriendo un arreglo con el orden de exploración en sentido inverso desde el otro extremo, para obtener las aristas que lo forman. También se usa una estructura complementaria, UnionFind(Ver \ref{alg:ej3:UF}) para detectar cuando una arista pertenece a dos componentes conexas distintas o pertenece a la misma y forma un ciclo.
\begin{algorithm}[h]
\KwData{aristas, cantidadNodos}

	bool encontreAnillo = false;
	Lista aristasDelAnillo;
	Lista aristasArbol;
	
	ListaAdyacencia grafo(cantNodos+1);
	
%	//Esta estructura se usará para quitar de la estructura principal las aristas que estén en el ciclo(O(n²))
	bool aristasAnillo[cantidadNodos+1][cantidadNodos+1];
	
	\ForAll{ (i,j) en aristasAnillo}{
				aristasAnillo[i][j] = false
	}
				
	%//O(n log(n))
	ordenar(aristas);
	
	UnionFind grupos(cantNodos);
	
	cantAristasEnArbol = 0;
	costoTotal = 0;
	
	\While{cantAristasEnArbol $<=$ cantNodos-1 and not aristas.vacia()}{
		arista = aristas.pop();
		
		\If{!grupos.find(arista.nodoU,arista.nodoV)}{
			%//Guardo las aristas del AGM
			aristasArbol.push(arista);
			
			costoTotal += arista.costo;
			grupos.unioN(arista.nodoU,arista.nodoV);
			
%			//Construyo AGM
			grafo[arista.nodoU].push(arista.nodoV);
			grafo[arista.nodoV].push(arista.nodoU);
			
			cantAristasEnArbol++;
			
		}\ElseIf{not encontreAnillo}{
			%//La primer arista que forme un ciclo pertenecerá a la solución ya que tiene peso minimo	
			encontreAnillo = true;
			
			costoTotal += arista.costo;			
			%//Hago DFS para recorrer el árbol y encontrar un camino entre los extremos de la arista que forma el ciclo
			
			aristasDelAnillo = encontrarCiclo(grafo, arista.nodoU,arista.nodoV);
			
			%//Marco en la matriz las aristas que pertenecen al  ciclo
			\ForAll{arista en aristasDelAnillo}{				
				aristasAnillo[arista.nodoU][arista.nodoV] = true;
				aristasAnillo[arista.nodoV][arista.nodoU] = true;
			}
			
			\ForAll{arista en aristasArbol}{
			%	//Las aristas que estan en el ciclo no tienen que estar en el resto de la estructura
				\If{aristasAnillo[arista.nodoU][arista.nodoV]}{
			%		//Al borrar se modifica el iterador siendo pos el siguiente elemento, por ende tenemos que modificarlo para que el bucle
			%		//no saltee elementos
					aristasArbol.borrar(arista);

				}
			}

		}
		
	}	
	
	\If{cantAristasEnArbol $\neq$ cantNodos-1 or not encontreAnillo }{
		return Solucion();
	}
	\Return Solucion(aristasDelAnillo,aristasArbol,costoTotal);
\caption{Kruskal modificado}
\label{alg:ej3:kruskal}
\end{algorithm}

\begin{algorithm}[h]
%//DFS
\KwData{grafo, nodoInicial, nodoFinal}

	Lista ciclo;
	bool nodoVisitado[grafo.size()]
	
	\ForAll{pos in nodoVisitado}{
		nodoVisitado[pos] = false
	}
	
	Pila pila;	
	int pred[grafo.size()];
	
	pred[nodoInicial] = 0;	
	pila.push(nodoInicial);	
	
	\While{not pila.empty()}{		
		nodo = pila.pop();

		nodoVisitado[nodo] = true;
		
		\For{hijo en grafo[nodo]}{
		
			\If{not nodoVisitado[hijo]}{
				pred[hijo] = nodo;
				pila.push(hijo);
			}
		}
	}
	ciclo.push(Arista(nodoInicial,nodoFinal,0));	
	nodo = nodoFinal;
		
	\While{pred[nodo] $\neq$ 0}{			
			ciclo.push(Arista(nodo,pred[nodo],0));
			nodo = pred[nodo];
		
	}	
	\Return ciclo;
	\caption{encontrarCiclo}
	\label{alg:ej3:dfs}
\end{algorithm}

\begin{function}[H]
%	//Cada nodo pertenece a un grupo diferente, el grupo se representa por la raíz del arbol que contiene
	int idGrupo[cantNodos+1];
	int sizeGrupo[cantNodos+1];
	
	\For {i = 1 hasta cantNodos}{
		idGrupo[i] = i;
		sizeGrupo[i] = 1;
	}	

\caption{UnionFind::UnionFind(cantidadNodos)}
\label{alg:ej3:UF}
\end{function}

\begin{function}[H]
	\Return raiz(nodoU) == raiz(nodoV);
\caption{UnionFind::find(nodoU,nodoV)}
\end{function}

\begin{function}[H]
%//Obtengo el representante del grupo(raíz del arbol)
	\While{nodo $\neq$ idGrupo[nodo]}{
		idGrupo[nodo] = idGrupo[idGrupo[nodo]];\tcp{path Compression}
		nodo = idGrupo[nodo];
	}
	
	\Return nodo;
\caption{UnionFind::raiz(nodo)}
\end{function}

\begin{function}[H]

	%//Obtengo los representantes de los grupos a los que pertenecen los nodos.
	i = raiz(nodoU);
	j = raiz(nodoV);

	%//El grupo que posee mas nodos conserva su representante, el que no, adopta el representante del otro.
	\If{sizeGrupo[i] $<$ sizeGrupo[j]}
	{
		idGrupo[i] = j;
		sizeGrupo[j] += sizeGrupo[i];
	}
	\Else
	{
		idGrupo[j] = i;
		sizeGrupo[i] += sizeGrupo[j];
	}	
	
\caption{ UnionFind::unioN(nodoU,nodoV) }
\end{function}



\section{Correctitud y Complejidad}

\subsection{Correctitud}

Dada una red de computadoras, el problema pide encontrar un una serie de enlaces entre las mismas de manera tal que todas queden interconectadas. Además debe existir un grupo de computadoras que estén conectadas en topología de anillo.
Para lograr esto se modelo el problema usando grafos, donde cada nodo representa una computadora y cada arista un enlace entre las mismas. La solución en el modelo es un AGM con una arista extra de peso mínimo.

Sabemos que un árbol generador mínimo conecta a todos los nodos minimizando la cantidad de aristas(y el peso total de las mismas). Dado que las aristas tienen peso positivo, un grafo con mas aristas será mas pesado:

sea $G(V,E)$ el grafo que representa a las computadoras y los enlaces entre estas, $T$ un árbol generador mínimo de $G$ y $G'$ un subgrafo conexo de $G$ tal que $V_{G'} = V_G$ se cumple:

$$
\#(E_T) \le \#(E_G')
$$
Porque un árbol generador tiene $n-1$ aristas\footnote{La cantidad mínima de aristas para que un grafo sea conexo}, donde $n$ es la cantidad de vértices de $G$ y las mismas tienen peso positivo. Si $T$ es mínimo entonces, tendremos una estructura que conecta a todos los nodos minimizando el costo total de aristas(enlaces).

Para generar un ciclo $T$ sabemos que solo tenemos que agregar una arista, agregando la que tiene peso mínimo de entre las que no pertenecen al árbol, mantenemos la condición de \textit{mínimo} de la estructura.


Se usa el algoritmo de \textit{Kruskal} para encontrar el AGM. Como la lista de aristas se evalúa de forma ordenada por peso\footnote{De menor a mayor}, cuando se encuentra la primera que forma un ciclo en la estructura que se está construyendo, se realiza un recorrido DFS partiendo de uno de los extremos de la misma, para encontrar el ciclo en cuestión. Esto se ejecuta solo una vez. Luego se continúa con la ejecución del algoritmo que encuentra el AGM.

Con un recorrido DFS podemos encontrar caminos desde la raíz a todos los nodos restantes. El ciclo lo encontramos registrando en cada nodo su antecesor en el recorrido y luego iterando desde el nodo final, en  este caso uno de los extremos de la arista que forma el ciclo, hasta el nodo raíz, el otro extremo de la arista en cuestión.

En la versión original de \textit{Kruskal}, cada vez que se encuentra una arista que forma un ciclo en la estructura en construcción, se omite. En nuestra versión, la primera que encuentra que cumple con esta condición es la que va a estar en nuestro grafo solución, porque es la que tiene peso mínimo.


\subsection{Complejidad}
Llamamos $n$ a la cantidad de nodos y $m$ a la de aristas.
En la línea 4 del algoritmo \ref{alg:ej3:kruskal} tenemos un costo de $\mathcal{O}(n^2)$, en la línea 6 se ordenan las aristas, $\mathcal{O}(m log(m))$. Inicializar la estructura \textit{UnionFind} pertenece a $\mathcal{O}(n)$, ver \ref{alg:ej3:UF}.
$$
m \le n(n-1)\frac{1}{2} = (n^2 - n)\frac{1}{2}
$$
$$
m \in \mathcal{O}(n^2 - n) = \mathcal{O}(n^2)-\mathcal{O}(n) \subset \mathcal{O}(n^2)
$$
$$
\mathcal{O}(m log(m)) \subset \mathcal{O}(n^2log(n^2)) \subset \mathcal{O}(n^2log(n))
$$
Entonces, Inicializar la estructura UnionFind, ordenar las aristas y recorrerlas todas \footnote{Inicialización necesaria para el procedimiento que encuentra el ciclo. Ver línea 4 del algoritmo \ref{alg:ej3:kruskal}} tiene el siguiente costo:
\begin{large}
$$
n + n^2 log(n) + n^2 \subset \mathcal{O}(n^2 log(n))
$$
\end{large}
Luego se repetirá un máximo de $m$ veces las líneas 10 a 15. Extraer un arista de la lista ordenada tiene costo constante al igual que agregarla a la lista solución.


Usar la técnica \textit{UnionFind}, $m$  operaciones de $union$ y $find$ tienen complejidad amortizada en tiempo\footnote{Capítulo 21. Introduction to Algorithms, 3rd Edition. Thomas H. Cormen} $O(m log (n))$ en términos de $n$: $O(n^2 log (n))$.

Resultando:
\begin{large}
$$
\mathcal{O}(n^2 log(n)) + \mathcal{O}(n^2 log(n)) \subset \mathcal{O}(n^2 log(n))
$$
\end{large}

Una sola vez se va a ejecutar el código de las líneas 17-24 que es el que encontrará el ciclo. Recorrer las listas de aristas costará $2m$ como máximo. El costo de la implementación de DFS es $n+2m$, porque al finalizar se genera la lista de aristas que pertenecen al camino de un extremo de la arista que genera el ciclo al otro.

Finalmente:
\begin{large}
$$
\mathcal{O}(n^2 log(n)) + \mathcal{O}(n+n^2) \subset \mathcal{O}(n^2 log(n))
$$
\end{large}

\subsection{Test de performance}
Para probar y medir el costo temporal del algoritmo buscamos correrlos con casos que para una misma cantidad de nodos, demanden la mayor cantidad de tiempo. Por la naturaleza del algoritmo vimos que, lo que fijaba la cota temporal era la cantidad de aristas que contiene el grafo y tiene sentido ya que pasando del modelo al caso real, en una red con muchos enlaces, tiene que ser mas difícil encontrar la solución óptima que en una con pocos. 

Es por esto que nuestro peor caso es un grafo completo, con lo cual, ordenar las aristas tiene la complejidad final del algoritmo y esto se debe hacer independientemente de sus pesos.

\newpage
En el gráfico \ref{fig:ej3:complejidad} vemos la comparación entre la complejidad teórica calculada y el tiempo de ejecución medido. Se puede apreciar como los tiempos se comportan como se esperaba.

\ponerGrafico{imagenes/ej3.pdf}{Complejidad teórica y tiempo de ejecución.}{1}{ej3:complejidad}
